package q1723_minimumTimeRequired;

import java.util.Arrays;

public class Solution {
    int[] jobs;
    int n;
    int k;
    int ans;
    /*
    跟2305题完全相同 但是在循环中加入了698的两个剪枝方式来加快速度
     */
    public int minimumTimeRequired(int[] jobs, int k) {
        this.jobs = jobs;
        this.k = k;
        this.n = jobs.length;
        ans = Integer.MAX_VALUE;
        // 排序非常重要 先发饼干较多的包，这样让回溯过程更快
        Arrays.sort(jobs);
        backtrack(new int[k], n - 1);

        return ans;
    }

    private void backtrack(int[] bucket, int start) {
        if (start < 0) {
            int cur = 0;
            for (int i : bucket) cur = Math.max(cur, i);

            ans = Math.min(cur, ans);
            return;
        }

        int zeroBucket = 0;
        for (int i : bucket) {
            if (i == 0) ++zeroBucket;
        }
        if (zeroBucket > start + 1) return;


        for (int i = 0; i < k; i++){
            if (bucket[i] > ans) return;
        }

        for (int i = 0; i < bucket.length; ++i) {
            if (bucket[i] + jobs[start] > ans) {
                continue;
            }
            bucket[i] += jobs[start];
            backtrack(bucket, start - 1);
            bucket[i] -= jobs[start];
            if (bucket[i] == 0) {
                // nums[index] 找不到可以凑成 target 的数
                break;
            }
        }
    }
}
